/**
 * 被围绕的区域
 *
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：
 * 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
 * 区域：连接所有 'O' 的单元格来形成一个区域。
 * 围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。
 * 通过 原地 将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。
 *
 * 示例 1：
 * 输入：board = [['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']]
 * 输出：[['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','O','X','X']]
 * 解释：
 * 在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。
 *
 * 示例 2：
 * 输入：board = [['X']]
 * 输出：[['X']]
 *
 * 提示：
 * m == board.length
 * n == board[i].length
 * 1 <= m, n <= 200
 * board[i][j] 为 'X' 或 'O'
 */

/**
 * 这题要是我们正面去处理的话会有点麻烦, 因为我们在更改的同时, 要注意这个最后是否
 * 与边界相连, 要是相连的话我们就要撤销之前的更改, 会很麻烦
 * 所以我们逆向思维, 我们先遍历与边界相连的 O 将相连的 O 全都改为 *
 * 不相连的还是 O
 * 最后在整体遍历一遍数组, 将 * 改为 O, 将 O 改为 X 就可以了
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n ^ 2)
 */

public class Main {

    // 定义全局变量
    int m, n;
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};

    public void solve(char[][] board) {

        // 初始化
        m = board.length;
        n = board[0].length;

        // 这里我们处理第一列和最后一列
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') changeArea(board, i, 0);
            if (board[i][n - 1] == 'O') changeArea(board, i, n - 1);
        }

        // 这里我们处理第一行和最后一行
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') changeArea(board, 0, i);
            if (board[m - 1][i] == 'O') changeArea(board, m - 1, i);
        }

        // 更改字符
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '*') board[i][j] = 'O';
            }
        }
    }

    public void changeArea(char[][] board, int a, int b) {

        // 这里递归处理相连的 O
        if (a >= 0 && a < m
                && b >= 0 && b < n
                && board[a][b] == 'O') {

            // 将与边界相连的 O 改成 *
            board[a][b] = '*';

            for (int i = 0; i < 4; i++) {

                int c = a + dx[i],
                        d = b + dy[i];

                // 递归处理相连的
                changeArea(board, c, d);
            }

        }
    }
}